布尔函数的表示与转换

$n$ 元布尔函数的定义如下：

f : GF (2)^{n} \to GF (2)

记为 $f (x)$ ，其中 $x$ 是定义在 $GF (2)$ 这个有限域上的 $n$ 元向量

如果我们已知一个函数它在对应输出下会输出什么，那么如何用布尔函数来描述它呢？

例如，有这样一个3比特内的代换密码 $y = f (x)$ ：

x	0	1	2	3	4	5	6	7
y	2	5	3	7	6	4	0	1
x	000	001	010	011	100	101	110	111
y	010	101	011	111	110	100	000	001

显然可以把这个问题分解成：分别求每一位所对应的布尔函数 $f_{0} (x), f_{1} (x), f_{2} (x)$
下面均仅讨论单独的一个布尔函数怎样表示，拿上面这个例子里的最高位举例

最简单的方法就是列真值表：

$x_{0}$	$x_{1}$	$x_{2}$	$f (x)$
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	0

但这肯定是不够的，因为我们需要用更数学的方式来表示，这样才能将问题导向一个数学领域，方便进行后续的形式化的研究
（如何判断是否数学呢？我认为是简洁+精确，通常来说就是在确保精确的前提下尽可能地简洁，如果可以的话，还得是直观的）

~~接下来我要做一个冗长且粗浅的剖析，可以跳过不看~~

我们知道，布尔函数是一个函数（这似乎是废话）
对于一个 $n$ 变元的布尔函数，给它输入 $n$ 个数，它就会返回一个数值
（所有这些数都是在 $G F (2)$ 上的，换句话说就是非0即1）

于是，我就可以把这个布尔函数 $f (x)$ 写成：

f (x) = f ([x_{1}, \dots, x_{n}]) = a_{0} + a_{1} x_{1} + \dots + a_{n} x_{n} + a_{n + 1} x_{1} x_{2} + \dots + a_{k} x_{1} \dots x_{n}

我们学计算机的一看就心领神会：啊呀！这不是解个方程就完事了吗？ $x$ 和 $f (x)$ 全是已知的，直接变成0-1整数规划问题交给计算机调用函数跑个结果就结束了

但如果是对于算法有那么一点了解（或者是学数学）的人，就会开始考虑：这复杂度太高了！ $k = 2^{n} - 1$ ，而宇宙所有粒子的数量也才只有大约 $10^{80} \approx (2^{10})^{25} = 2^{250}$ 个，随便搞一个1024bit的输入都算不动

这条路暂时没想法了，所以先把它放在一边，现在来换一个思路：

f (x) = {\begin{aligned} 0 & x = [0, 0, 0] \\ 1 & x = [0, 0, 1] \\ \dots \\ 0 & x = [1, 1, 1] \end{aligned}

emmm，你可能会想：这跟全是if语句的si山代码有什么区别？！
的确是这样，因此，我们还得用数学的方式让它更简洁一些

由于输入输出都是非0即1的，这给了我们很大的便利（这样说好像有点本末倒置，毕竟可能正是因为布尔代数很方便才衍生出了电脑的二进制）
抽象一点写就是：
$f (x) = (x ? = 0) a_{0} + (x ? = 1) a_{1} + \dots + (x ? = 2^{n} - 1) a_{2^{n} - 1}$
上式的意思是，如果 $x$ 等于某个值，那么就加上对应的那个结果，否则就加上0（相当于什么也没加），最终的效果和前面的 if 语句条件判断是等价的

那么如何表示其中的 $(x ? = c_{i}), c_{i} \in [0, 2^{n} - 1]$ 呢？

待续